package medium;//给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
//
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
//
// 此外，你可以假设该网格的四条边均被水包围。
//
//
//
// 示例 1：
//
//
//输入：grid = [
//  ["1","1","1","1","0"],
//  ["1","1","0","1","0"],
//  ["1","1","0","0","0"],
//  ["0","0","0","0","0"]
//]
//输出：1
//
//
// 示例 2：
//
//
//输入：grid = [
//  ["1","1","0","0","0"],
//  ["1","1","0","0","0"],
//  ["0","0","1","0","0"],
//  ["0","0","0","1","1"]
//]
//输出：3
//
//
//
//
// 提示：
//
//
// m == grid.length
// n == grid[i].length
// 1 <= m, n <= 300
// grid[i][j] 的值为 '0' 或 '1'
//
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵
// 👍 1280 👎 0


import java.util.ArrayDeque;
import java.util.Deque;

//leetcode submit region begin(Prohibit modification and deletion)
public class L200 {
    public static int numIslands(char[][] grid) {
        //广度优先搜索，时间和空间都是O(n)
        int rows = grid.length;
        int column = grid[0].length;
        Deque<Integer> deque = new ArrayDeque<>();
        int count = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < column; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    int x = column * i + j;
                    deque.offerLast(x);
                    grid[i][j] = '0';
                    while (!deque.isEmpty()) {
                        Integer pollLast = deque.pollLast();
                        int c = pollLast % column;
                        int r = pollLast / column;
                        if (r + 1 < rows && grid[r + 1][c] == '1') {
                            deque.offerLast((r + 1) * column + c);
                            grid[r + 1][c] = '0';
                        }
                        if (r - 1 > -1 && grid[r - 1][c] == '1') {
                            deque.offerLast((r - 1) * column + c);
                            grid[r - 1][c] = '0';
                        }
                        if (c + 1 < column && grid[r][c + 1] == '1') {
                            deque.offerLast(r * column + c + 1);
                            grid[r][c + 1] = '0';
                        }
                        if (c - 1 > -1 && grid[r][c - 1] == '1') {
                            deque.offerLast(r * column + c - 1);
                            grid[r][c - 1] = '0';
                        }
                    }
                }
            }
        }
        return count;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
